import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {

    /*
    * TreeNode 类：定义了一个简单的二叉树节点类，包含节点值 val，左子节点 left，右子节点 right。
isValidBST 方法：调用带有上下界的辅助方法来检查整个树是否为二叉搜索树。
isValidBST 辅助方法：递归地检查每个节点的值是否在合法范围内，并递归检查其左右子树。

    如果当前节点为空，返回 true，表示到达了叶子节点的子节点，未发现任何问题。
    检查当前节点的值是否在 [lower, upper) 范围内，如果不在，返回 false。
    递归检查左子树和右子树，更新上下界：
        对左子树，当前节点的值是新的上界。
        对右子树，当前节点的值是新的下界。
*/
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }


    //非递归
    public boolean isValidBST2(TreeNode root) {
        if (root == null) {
            return true;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode previous = null;

        while (current != null || !stack.isEmpty()) {
            // 将所有左子节点压入栈中
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            // 处理栈顶节点
            current = stack.pop();

            // 检查当前节点是否大于前一个节点
            if (previous != null && current.val <= previous.val) {
                return false;
            }

            // 更新前一个节点
            previous = current;

            // 处理右子节点
            current = current.right;
        }

        return true;
    }


    public static void main(String[] args) {
        // 构建二叉树
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        // 检查是否为二叉搜索树
        Solution solution = new Solution();
        System.out.println(solution.isValidBST(root));  // 输出: true
    }
}
